package algorithm;

import tree.TrieDictionary;

import java.util.HashSet;
import java.util.List;
import java.util.LinkedList;
/**
 * http://en.wikipedia.org/wiki/Boggle
 * 
 * @author michaelyi
 */
public class Boggle {
	private final static String DICTIONARY_NAME = "dictionary.txt";
	
	private final TrieDictionary dictionary;
	private final char[][] board;
	
	/**
	 * 
	 */
	public Boggle(char[][] board) {
		this.dictionary = TrieDictionary.buildDictionary(System.getProperty("user.dir") + "/" + DICTIONARY_NAME);
		this.board = board;
	}
	
	public List<String> getBoggleWords() {
		HashSet<String> words = new HashSet<String>();
		
		int rows = board.length;
		int cols = board[0].length;
		boolean[][] flags = new boolean[rows][cols]; // false is not visited, true is visited
		
		StringBuilder sb = new StringBuilder();
		for (int row = 0; row < rows; ++row) {
			for (int col = 0; col < cols; ++col) {
				backtrack(row, col, words, flags, sb);
				sb.setLength(0);
			}
		}
		
		return new LinkedList<String>(words);
	}
	
	private void backtrack(int row, int col, HashSet<String> words, boolean[][] flags, StringBuilder prefix) {
		
		int rows = board.length;
		int cols = board[0].length;
		assert(row >= -1 && row <= rows);
		assert(col >= -1 && col <= cols);
		
		if (row == -1)
			row = rows - 1;
		else if (row == rows)
			row = 0;
		
		if (col == -1)
			col = cols - 1;
		else if (col == cols)
			col = 0;
		
		if (flags[row][col])
			return;
		else {
			flags[row][col] = true;
			prefix.append(board[row][col]);
		}
		
		if (dictionary.countWords(prefix.toString()) > 0) {
			if (prefix.length() >= 4)
				words.add(prefix.toString());
		}

		if (dictionary.countPrefixes(prefix.toString()) > 0) {
			// Traverse whole board by backtracking
			// Visiting order: left, left_bottom, down, right_bottom, right, top_right, top, top_left
			backtrack(row, col+1, words, flags, prefix);
			
			backtrack(row+1, col+1, words, flags, prefix);
			
			backtrack(row+1, col, words, flags, prefix);
			
			backtrack(row+1, col-1, words, flags, prefix);
			
			backtrack(row, col-1, words, flags, prefix);
			
			backtrack(row-1, col-1, words, flags, prefix);
			
			backtrack(row-1, col, words, flags, prefix);
			
			backtrack(row-1, col+1, words, flags, prefix);
		}
		
		prefix.deleteCharAt(prefix.length() - 1);
		flags[row][col] = false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char[][] board = new char[][]{ {'e', 'z', 's', 'u'}, 
									   {'e', 'o', 's', 'e'},
									   {'f', 'e', 'a', 'i'},
									   {'a', 'y', 'o', 'l'} };
									   
		
		board = new char[][]{ {'a', 'n', 'o', 's'}, 
							  {'s', 't', 'o', 'c'},
							  {'r', 'e', 'v', 'h'},
							  {'p', 'm', 'a', 'l'} };
					
		Boggle boggle = new Boggle(board);
		List<String> words = boggle.getBoggleWords();
		for (String word : words) {
			System.out.printf("%s\n", word);
		}
	}

}
